/**
 *
 将一个字符串str的内容颠倒过来，并输出。str的长度不超过100个字符。 如：输入“I am a student”，输出“tneduts a ma I”。
 *
 *
 * @author: YuanChilde
 * @date: 2020-02-17 8:01
 * @version: 1.0
 * Modification History:
 * Date    Author      Version     Description
 * -----------------------------------------------------------------
 * 2020-02-17 8:01    YuanChilde     1.0        新增
 */
public class BeiBao {

    public static void main(String[] args){
       /* Scanner sc = new Scanner(System.in);*/
    }

    /**
     *
     * @param weight   物品的重量数组
     * @param value 物品的价值数据
     * @param n 物品总数
     * @param w 最大容量
     */
    public int getMaxValue(int[] weight,int[] value,int n, int w){
        int[][] states = new int[n][w+1];
        // 初始化数据
        for(int i = 0;i<n;i++){
            for (int y = 0;y<w+1;y++){
                states[i][y] = -1;
            }
        }
        // 设置第一行数据
        states[0][0] = 0;
        states[0][weight[0]] = 0;

        for(int i = 1;i<n;i++){
            // 第一步不加入背包的分支
            for (int y = 0;y<=w;y++){
                if(states[i-1][y] >= 0){
                    states[i][y] = states[i-1][y];
                }
            }
            // 第二步加入背包的分支
            for (int y = 0; y <= w - weight[i]; y++) {
                // 只处理上一行存在数据的格子
                if (states[i - 1][y] >= 0) {
                    // 上行的列计算其价值
                    int v = states[i - 1][y] + value[i];
                    if (v > states[i][y+ weight[i]]) {
                        states[i][y+weight[i]] = v;
                    }
                }
            }
        }

        int maxValue = -1;
        for (int y = 0; y <= w; y++) {
            if (states[n - 1][y] > maxValue) {
                maxValue = states[n - 1][y];
            }
        }
        return 0;
    }
}
